{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Work Sessions to Finish the Tasks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSessions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完成任务的最少工作时间段"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你被安排了 <code>n</code>&nbsp;个任务。任务需要花费的时间用长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>tasks</code>&nbsp;表示，第 <code>i</code>&nbsp;个任务需要花费&nbsp;<code>tasks[i]</code>&nbsp;小时完成。一个 <strong>工作时间段</strong>&nbsp;中，你可以 <strong>至多</strong>&nbsp;连续工作&nbsp;<code>sessionTime</code>&nbsp;个小时，然后休息一会儿。</p>\n",
    "\n",
    "<p>你需要按照如下条件完成给定任务：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果你在某一个时间段开始一个任务，你需要在 <strong>同一个</strong>&nbsp;时间段完成它。</li>\n",
    "\t<li>完成一个任务后，你可以 <strong>立马</strong>&nbsp;开始一个新的任务。</li>\n",
    "\t<li>你可以按 <strong>任意顺序</strong>&nbsp;完成任务。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你&nbsp;<code>tasks</code> 和&nbsp;<code>sessionTime</code>&nbsp;，请你按照上述要求，返回完成所有任务所需要的&nbsp;<strong>最少</strong>&nbsp;数目的&nbsp;<strong>工作时间段</strong>&nbsp;。</p>\n",
    "\n",
    "<p>测试数据保证&nbsp;<code>sessionTime</code> <strong>大于等于</strong>&nbsp;<code>tasks[i]</code>&nbsp;中的&nbsp;<strong>最大值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [1,2,3], sessionTime = 3\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>你可以在两个工作时间段内完成所有任务。\n",
    "- 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。\n",
    "- 第二个工作时间段：完成第三个任务，花费 3 小时。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [3,1,3,1,1], sessionTime = 8\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>你可以在两个工作时间段内完成所有任务。\n",
    "- 第一个工作时间段：完成除了最后一个任务以外的所有任务，花费 3 + 1 + 3 + 1 = 8 小时。\n",
    "- 第二个工作时间段，完成最后一个任务，花费 1 小时。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>tasks = [1,2,3,4,5], sessionTime = 15\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>你可以在一个工作时间段以内完成所有任务。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == tasks.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 14</code></li>\n",
    "\t<li><code>1 &lt;= tasks[i] &lt;= 10</code></li>\n",
    "\t<li><code>max(tasks[i]) &lt;= sessionTime &lt;= 15</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-work-sessions-to-finish-the-tasks](https://leetcode.cn/problems/minimum-number-of-work-sessions-to-finish-the-tasks/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-work-sessions-to-finish-the-tasks](https://leetcode.cn/problems/minimum-number-of-work-sessions-to-finish-the-tasks/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n3', '[3,1,3,1,1]\\n8', '[1,2,3,4,5]\\n15']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        # 枚举子集的dp\n",
    "        # 位运算优化\n",
    "        n=len(tasks)\n",
    "        dp=[n<<4]*(1<<n)\n",
    "        dp[0]=1<<4\n",
    "\n",
    "        for task in range(1,1<<n):\n",
    "            for i in range(n):\n",
    "                if task&(1<<i):\n",
    "                    tas=task-(1<<i)\n",
    "                    if dp[tas]%(1<<4)+tasks[i]<=sessionTime: # 状态转移判断\n",
    "                        dp[task]=min(dp[task],dp[tas]+tasks[i])\n",
    "                    else:\n",
    "                        dp[task]=min(dp[task],((dp[tas]>>4)+1<<4)+tasks[i])\n",
    "        return dp[(1<<n)-1]>>4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        random.seed(2023)\n",
    "        self.ans = float('inf')\n",
    "\n",
    "\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        for _ in range(50): # 可以继续调参往低走\n",
    "            random.shuffle(tasks)\n",
    "            self.sa(tasks.copy(), sessionTime, 1e7, 0.9, 1e-4) # 继续初始温度越低也可以\n",
    "\n",
    "        return self.ans \n",
    "       \n",
    "    \n",
    "    \n",
    "    def energy(self, z, limit):\n",
    "        e = 0\n",
    "        n = len(z)\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            if s + z[i] <= limit:\n",
    "                s += z[i]\n",
    "            else:\n",
    "                e += 1\n",
    "                s = z[i]\n",
    "        if z[i] > 0:\n",
    "            e += 1\n",
    "        self.ans = min(self.ans, e)\n",
    "        return e\n",
    "    \n",
    "\n",
    "    def sa(self, z, limit, T, fa, low):\n",
    "\n",
    "        while T > low:\n",
    "            T *= fa\n",
    "            e1 = self.energy(z, limit)\n",
    "            n = len(z)\n",
    "            if n == 1:\n",
    "                return \n",
    "            while True:\n",
    "                a = random.randint(0, n-1)\n",
    "                b = random.randint(0, n-1)\n",
    "                if a != b:\n",
    "                    break\n",
    "            z[a], z[b] = z[b], z[a]\n",
    "\n",
    "            e2 = self.energy(z, limit) \n",
    "            dt = e2 - e1\n",
    "            if dt >= 0 and math.exp(-dt/T) > random.random():\n",
    "                z[a], z[b] = z[b], z[a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        # 枚举子集的dp\n",
    "        # 位运算优化\n",
    "        n=len(tasks)\n",
    "        dp=[n<<4]*(1<<n)\n",
    "        dp[0]=1<<4\n",
    "\n",
    "        for task in range(1,1<<n):\n",
    "            for i in range(n): # 子集枚举\n",
    "                if task&(1<<i):\n",
    "                    tas=task-(1<<i)\n",
    "                    if dp[tas]%(1<<4)+tasks[i]<=sessionTime: # 状态转移判断\n",
    "                        dp[task]=min(dp[task],dp[tas]+tasks[i])\n",
    "                    else:\n",
    "                        dp[task]=min(dp[task],((dp[tas]>>4)+1<<4)+tasks[i])\n",
    "        return dp[(1<<n)-1]>>4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        tasks.sort(reverse = True)\n",
    "        l,r = 1,n+1\n",
    "        # erfen\n",
    "        def check(k,start,buket):\n",
    "            if start >= n:\n",
    "                return True\n",
    "            for i in range(k):\n",
    "                if buket[i]+tasks[start]>sessionTime:\n",
    "                    continue\n",
    "                else:\n",
    "                    buket[i] += tasks[start]\n",
    "                    if check(k,start+1,buket):\n",
    "                        return True\n",
    "                    buket[i] -= tasks[start]\n",
    "                    if buket[i] == 0 or  buket[i] == sessionTime:\n",
    "                        return False\n",
    "            return False\n",
    "            \n",
    "        while l<r:\n",
    "            mid = l +(r-l)//2\n",
    "            if check(mid,0,[0]*mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid +1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        inf = float('inf')\n",
    "        dp = [inf for _  in range(1 << n)]\n",
    "        dp[0] = 0\n",
    "        def fun(s):\n",
    "            return sum(tasks[i] if (s >> i) & 1 == 1 else 0 for i in range(n))\n",
    "        valid = []\n",
    "        for i in range(1 << n):\n",
    "            if fun(i) <= sessionTime:\n",
    "                valid.append(True)\n",
    "            else:\n",
    "                valid.append(False)\n",
    "\n",
    "        for s in range(1 << n):\n",
    "            sub = s\n",
    "            while sub:\n",
    "                if valid[sub]:\n",
    "                    rest = s ^ sub\n",
    "                    dp[s] = min(dp[s], dp[rest] + 1)\n",
    "                sub = (sub - 1) & s\n",
    "            # print(s, bin(s), dp[s])\n",
    "        return dp[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        valid = [False] * (1 << n)\n",
    "        for mask in range(1, 1 << n):\n",
    "            needTime = 0\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i):\n",
    "                    needTime += tasks[i]\n",
    "            if needTime <= sessionTime:\n",
    "                valid[mask] = True\n",
    "\n",
    "        f = [float(\"inf\")] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for mask in range(1, 1 << n):\n",
    "            subset = mask\n",
    "            while subset:\n",
    "                if valid[subset]:\n",
    "                    f[mask] = min(f[mask], f[mask ^ subset] + 1)\n",
    "                subset = (subset - 1) & mask\n",
    "        \n",
    "        return f[(1 << n) - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "    \n",
    "        n = len(tasks)\n",
    "        S = [0] * (1 << n)\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, 1 << i):\n",
    "                S[j | 1 << i] = S[j] + tasks[i]\n",
    "        \n",
    "\n",
    "        f = [n] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for to_task in range(1 << n):\n",
    "            sub = to_task\n",
    "            while sub:\n",
    "                if S[sub] <= sessionTime:\n",
    "                    f[to_task] = min(f[to_task], f[to_task^sub] + 1)\n",
    "                sub = (sub-1) & to_task\n",
    "        \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        random.seed(2023)\n",
    "        self.ans = float('inf')\n",
    "\n",
    "\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        for _ in range(int(2*len(tasks))): # 可以继续调参往低走\n",
    "            random.shuffle(tasks)\n",
    "            self.sa(tasks.copy(), sessionTime, 1e7, 0.9, 1e-4) # 继续初始温度越低也可以\n",
    "\n",
    "        return self.ans \n",
    "       \n",
    "    \n",
    "    \n",
    "    def energy(self, z, limit):\n",
    "        e = 0\n",
    "        n = len(z)\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            if s + z[i] <= limit:\n",
    "                s += z[i]\n",
    "            else:\n",
    "                e += 1\n",
    "                s = z[i]\n",
    "        if z[i] > 0:\n",
    "            e += 1\n",
    "        self.ans = min(self.ans, e)\n",
    "        return e\n",
    "    \n",
    "\n",
    "    def sa(self, z, limit, T, fa, low):\n",
    "\n",
    "        while T > low:\n",
    "            T *= fa\n",
    "            e1 = self.energy(z, limit)\n",
    "            n = len(z)\n",
    "            if n == 1:\n",
    "                return \n",
    "            while True:\n",
    "                a = random.randint(0, n-1)\n",
    "                b = random.randint(0, n-1)\n",
    "                if a != b:\n",
    "                    break\n",
    "            z[a], z[b] = z[b], z[a]\n",
    "\n",
    "            e2 = self.energy(z, limit) \n",
    "            dt = e2 - e1\n",
    "            if dt >= 0 and math.exp(-dt/T) > random.random():\n",
    "                z[a], z[b] = z[b], z[a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "    \n",
    "        n = len(tasks)\n",
    "        S = [0] * (1 << n)\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, 1 << i):\n",
    "                S[j | 1 << i] = S[j] + tasks[i]\n",
    "        \n",
    "\n",
    "        f = [n] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for to_task in range(1 << n):\n",
    "            sub = to_task\n",
    "            while sub:\n",
    "                if S[sub] <= sessionTime:\n",
    "                    f[to_task] = min(f[to_task], f[to_task^sub] + 1)\n",
    "                sub = (sub-1) & to_task\n",
    "        \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        m = len(tasks)\n",
    "        m = 1<< m \n",
    "        dp = [inf] * m \n",
    "        for i in range(1,m):\n",
    "            state = i \n",
    "            speed  = 0 \n",
    "            idx = 0\n",
    "            while state != 0:\n",
    "                if state&1 :\n",
    "                    speed += tasks[idx]\n",
    "                state >>= 1\n",
    "                idx += 1\n",
    "            if speed <= sessionTime:\n",
    "                dp[i] = 1\n",
    "        for i in range(1,m):\n",
    "            if dp[i] == 1:\n",
    "                continue\n",
    "            # for j in range(1,i):\n",
    "            #     if (j|i) == i :\n",
    "            #         dp[i]=min(dp[i],dp[j]+dp[i^j])\n",
    "            split = i >> 1\n",
    "            j = (i - 1) & i \n",
    "            while j > split:\n",
    "                 dp[i]=min(dp[i],dp[j]+dp[i^j])\n",
    "                 j = (j-1)& i \n",
    "                \n",
    "\n",
    "        return dp[m-1] \n",
    "                \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dic = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            for j in range(n):\n",
    "                if i & (1 << j):\n",
    "                    dic[i] += nums[j]\n",
    "        f = [n] * (1 << n)  # 选择某几个的最少花销\n",
    "        for i in range(1 << n):\n",
    "            if dic[i] <= target:\n",
    "                f[i] = 1\n",
    "                continue\n",
    "            j = i\n",
    "            while j:\n",
    "                if dic[j] <= target:\n",
    "                    f[i] = min(f[i], f[j] + f[i^j]);\n",
    "                j = (j - 1) & i \n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        INF = 10 ** 9\n",
    "        n = len(tasks)\n",
    "        \n",
    "        sum = [0 for _ in range(1 << n)]\n",
    "        for state in range(1 << n):\n",
    "            for i in range(n):\n",
    "                if (state >> i) & 1:\n",
    "                    sum[state] += tasks[i]\n",
    "        \n",
    "        dp = [inf for _ in range(1 << n)]\n",
    "        dp[0] = 0\n",
    "        \n",
    "        for state in range(1, 1 << n):\n",
    "            sub = state\n",
    "            while sub:\n",
    "                if sum[sub] <= sessionTime:\n",
    "                    dp[state] = min(dp[state], dp[state ^ sub] + 1)\n",
    "                \n",
    "                sub = (sub - 1) & state\n",
    "        \n",
    "        return dp[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        arr = []\n",
    "        n = len(tasks)\n",
    "        for s in range(1 << n):\n",
    "            tot = 0\n",
    "            for i in range(n):\n",
    "                if s >> i & 1:\n",
    "                    tot += tasks[i]\n",
    "            arr.append(tot)\n",
    "        f = [n] * len(arr)\n",
    "        f[0] = 0\n",
    "        for s in range(1, 1 << n):\n",
    "            sub = s\n",
    "            while sub:\n",
    "                if arr[sub] <= sessionTime:\n",
    "                    f[s] = min(f[s], f[s ^ sub] + 1)\n",
    "                sub = (sub - 1) & s\n",
    "        return f[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        # def lt1986_2(tasks,sessionTime):\n",
    "        #     def iteration(tasks):\n",
    "        #         left=[]\n",
    "        #         temp=0\n",
    "        #         for e in tasks:\n",
    "        #             if temp+e<=sessionTime:\n",
    "        #                 temp+=e\n",
    "        #             else:\n",
    "        #                 left.append(e)\n",
    "        #         if not left:return 1\n",
    "        #         else:return 1+iteration(left)\n",
    "        #     tasks.sort(reverse=True)\n",
    "        #     return iteration(tasks)\n",
    "        # return lt1986_2(tasks,sessionTime)\n",
    "\n",
    "        # def lt1986(tasks,sessionTime):\n",
    "        #     n=len(tasks)\n",
    "        #     d=defaultdict(int)\n",
    "        #     def dfs(mask):\n",
    "        #         if not d[mask]:\n",
    "        #             s='0'*(n-len(bin(mask))+2)+bin(mask)[2:]\n",
    "        #             if sum([ int(s[i])*tasks[i] for i in range(n)  ])<=sessionTime:\n",
    "        #                 d[mask]=1\n",
    "        #             else:\n",
    "        #                 s1=mask\n",
    "        #                 temp=[]\n",
    "        #                 while s1!=0:\n",
    "        #                     s2=s1^mask\n",
    "        #                     if s2<s1<mask:temp.append(dfs(s1)+dfs(s2))\n",
    "        #                     s1=(s1-1)&mask\n",
    "        #                 d[mask]=min(temp)\n",
    "        #         return d[mask]\n",
    "        #     return dfs((1<<n)-1)\n",
    "        # return lt1986(tasks,sessionTime)\n",
    "\n",
    "        def lt1986_dp(tasks,sessionTime):\n",
    "            n=len(tasks)\n",
    "            dp=[0]*(1<<n)\n",
    "            def get_sum(i):\n",
    "                idx = n - 1\n",
    "                res = 0\n",
    "                while i > 0:\n",
    "                    last_digit = i & 1\n",
    "                    res += tasks[idx] if last_digit else 0\n",
    "                    idx -= 1\n",
    "                    i >>= 1\n",
    "                return res\n",
    "            for i in range(1<<n):\n",
    "                temp=get_sum(i)\n",
    "                if temp<=sessionTime:dp[i]=1\n",
    "            for i in range(1<<n):\n",
    "                if dp[i]!=1:\n",
    "                    s1,temp=i,[]\n",
    "                    while s1>0:\n",
    "                        s2=i^s1\n",
    "                        if s2<s1<i:temp.append(dp[s1]+dp[s2])\n",
    "                        if s2>=s1:break\n",
    "                        s1=(s1-1)&i\n",
    "                    dp[i]=min(temp)\n",
    "            return dp[-1]\n",
    "        return lt1986_dp(tasks,sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        ret = 0\n",
    "        n = len(tasks)\n",
    "        f = [1 << 30] * (1 << n)\n",
    "        f[0] = 0\n",
    "        ok = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            s = 0\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    s += tasks[j]\n",
    "            ok[i] = s <= sessionTime\n",
    "        for mask in range(1, 1 << n):\n",
    "            submask = mask\n",
    "            while submask:\n",
    "                if ok[submask]:\n",
    "                    f[mask] = min(f[mask], f[mask ^ submask] + 1)\n",
    "                submask = (submask - 1) & mask\n",
    "        return f[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        INF = 10 ** 9\n",
    "        n = len(tasks)\n",
    "        \n",
    "        sum = [0 for _ in range(1 << n)]\n",
    "        for state in range(1 << n):\n",
    "            for i in range(n):\n",
    "                if (state >> i) & 1:\n",
    "                    sum[state] += tasks[i]\n",
    "        \n",
    "        dp = [INF for _ in range(1 << n)]\n",
    "        dp[0] = 0\n",
    "        \n",
    "        for state in range(1, 1 << n):\n",
    "            sub = state\n",
    "            while sub:\n",
    "                if sum[sub] <= sessionTime:\n",
    "                    dp[state] = min(dp[state], dp[state ^ sub] + 1)\n",
    "                \n",
    "                sub = (sub - 1) & state\n",
    "        \n",
    "        return dp[(1 << n) - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        tasks.sort(reverse=True)\n",
    "        self.tasks = tasks\n",
    "        self.n = len(tasks)\n",
    "        self.sessionTime = sessionTime\n",
    "        self.res = float('inf')\n",
    "        self.session = [0] * self.n\n",
    "        self.dfs(0, 1)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, index, session_count):\n",
    "        if index >= self.n or session_count >= self.n:\n",
    "            self.res = min(self.res, session_count)\n",
    "            return\n",
    "        if session_count >= self.res:\n",
    "            return\n",
    "        for i in range(session_count):\n",
    "            if self.session[i] + self.tasks[index] <= self.sessionTime:\n",
    "                if i > 0 and self.session[i - 1] == self.session[i]:\n",
    "                    continue\n",
    "                self.session[i] += self.tasks[index]\n",
    "                self.dfs(index + 1, session_count)\n",
    "                self.session[i] -= self.tasks[index]\n",
    "        self.session[session_count] += self.tasks[index]\n",
    "        self.dfs(index + 1, session_count + 1)\n",
    "        self.session[session_count] -= self.tasks[index]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        ans = n\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                nonlocal ans\n",
    "                ans = min(ans,len(path))\n",
    "                return\n",
    "            # 剪枝，没有当前答案优\n",
    "            if len(path) >= ans:\n",
    "                return\n",
    "            # 当前任务要么加入到已有的时间段，要么新开一个时间段\n",
    "            # 加入当前已有时间段\n",
    "            for j,t in enumerate(path):\n",
    "                # 排除等效冗余\n",
    "                if j and t == path[j - 1]:\n",
    "                    continue\n",
    "                if t + tasks[i] <= sessionTime:\n",
    "                    path[j] += tasks[i]\n",
    "                    dfs(i + 1)\n",
    "                    path[j] -= tasks[i]\n",
    "            # 新开一个\n",
    "            path.append(tasks[i])\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        if sum(tasks) <= sessionTime:\n",
    "            return 1\n",
    "        tasks.sort(reverse=True)\n",
    "        \n",
    "        def check(x):\n",
    "            bucket = [0] * x\n",
    "            def dfs(u):\n",
    "                if u == len(tasks):\n",
    "                    return True\n",
    "                for i in range(x):\n",
    "                    if i >= 1 and bucket[i-1] == bucket[i]:\n",
    "                        continue\n",
    "                    if tasks[u] + bucket[i] <= sessionTime:\n",
    "                        bucket[i] += tasks[u]\n",
    "                        if dfs(u + 1):\n",
    "                            return True\n",
    "                        bucket[i] -= tasks[u]\n",
    "                return False\n",
    "            return dfs(0)\n",
    "        left, right = 1, len(tasks) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = left + right >> 1\n",
    "            if check(mid): right = mid\n",
    "            else: left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        random.seed(2023)\n",
    "        self.ans = float('inf')\n",
    "\n",
    "\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        for _ in range(20): # 可以继续调参往低走\n",
    "            random.shuffle(tasks)\n",
    "            self.sa(tasks.copy(), sessionTime, 1e7, 0.9, 1e-4) # 继续初始温度越低也可以\n",
    "\n",
    "        return self.ans \n",
    "       \n",
    "    \n",
    "    \n",
    "    def energy(self, z, limit):\n",
    "        e = 0\n",
    "        n = len(z)\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            if s + z[i] <= limit:\n",
    "                s += z[i]\n",
    "            else:\n",
    "                e += 1\n",
    "                s = z[i]\n",
    "        if z[i] > 0:\n",
    "            e += 1\n",
    "        self.ans = min(self.ans, e)\n",
    "        return e\n",
    "    \n",
    "\n",
    "    def sa(self, z, limit, T, fa, low):\n",
    "\n",
    "        while T > low:\n",
    "            T *= fa\n",
    "            e1 = self.energy(z, limit)\n",
    "            n = len(z)\n",
    "            if n == 1:\n",
    "                return \n",
    "            while True:\n",
    "                a = random.randint(0, n-1)\n",
    "                b = random.randint(0, n-1)\n",
    "                if a != b:\n",
    "                    break\n",
    "            z[a], z[b] = z[b], z[a]\n",
    "\n",
    "            e2 = self.energy(z, limit) \n",
    "            dt = e2 - e1\n",
    "            if dt >= 0 and math.exp(-dt/T) > random.random():\n",
    "                z[a], z[b] = z[b], z[a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "\n",
    "        n = len(tasks)\n",
    "        dp = [n] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        valid = [False] * (1 << n)\n",
    "        for mask in range(1 << n):\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += tasks[i]\n",
    "            if cnt <= sessionTime:\n",
    "                valid[mask] = True\n",
    "\n",
    "        for mask in range(1, 1 << n):\n",
    "            cur = mask\n",
    "            while cur:\n",
    "                if valid[cur]:\n",
    "                    dp[mask] = min(dp[mask], dp[mask ^ cur] + 1)\n",
    "                cur = mask & (cur - 1)\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        if sum(tasks) <= sessionTime:\n",
    "            return 1\n",
    "        tasks.sort(reverse = True)\n",
    "        left = 2\n",
    "        right = len(tasks)\n",
    "\n",
    "\n",
    "        def check(tar):\n",
    "            bucket = [0] * tar\n",
    "\n",
    "            def dfs(cur):\n",
    "                if cur == len(tasks):\n",
    "                    return True\n",
    "\n",
    "                for i in range(tar):\n",
    "                    if i != 0 and bucket[i] == bucket[i - 1]:\n",
    "                        continue\n",
    "\n",
    "                    if bucket[i] + tasks[cur] <= sessionTime:\n",
    "                        bucket[i] += tasks[cur]\n",
    "                        if dfs(cur + 1):\n",
    "                            return True\n",
    "                        bucket[i] -= tasks[cur]\n",
    "                \n",
    "                return False\n",
    "\n",
    "\n",
    "            return dfs(0)\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        tasks.sort(reverse = True) # 先搜大的任务\n",
    "        n = len(tasks)\n",
    "        ans = n\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            # 剪枝，没有当前答案优\n",
    "            if len(path) >= ans:\n",
    "                return\n",
    "            if i == n:\n",
    "                ans = len(path)\n",
    "                return\n",
    "            # 当前任务要么加入到已有的时间段，要么新开一个时间段\n",
    "            # 加入当前已有时间段\n",
    "            for j,t in enumerate(path):\n",
    "                # 排除等效冗余\n",
    "                if j and t == path[j - 1]:\n",
    "                    continue\n",
    "                if t + tasks[i] <= sessionTime:\n",
    "                    path[j] += tasks[i]\n",
    "                    dfs(i + 1)\n",
    "                    path[j] -= tasks[i]\n",
    "            # 新开一个\n",
    "            path.append(tasks[i])\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        tasks.sort(reverse = True) # 先搜大的任务\n",
    "        n = len(tasks)\n",
    "        ans = n\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            # 剪枝，没有当前答案优\n",
    "            if len(path) >= ans:\n",
    "                return\n",
    "            if i == n:\n",
    "                ans = len(path)\n",
    "                return\n",
    "            # 当前任务要么加入到已有的时间段，要么新开一个时间段\n",
    "            # 加入当前已有时间段\n",
    "            for j,t in enumerate(path):\n",
    "                # 排除等效冗余\n",
    "                if j and t == path[j - 1]:\n",
    "                    continue\n",
    "                if t + tasks[i] <= sessionTime:\n",
    "                    path[j] += tasks[i]\n",
    "                    dfs(i + 1)\n",
    "                    path[j] -= tasks[i]\n",
    "            # 新开一个\n",
    "            path.append(tasks[i])\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        self.tasks = tasks\n",
    "        self.sessionTime = sessionTime\n",
    "        self.memo = [-1]*(1 << len(tasks))\n",
    "        return self.dfs((1 << len(tasks))-1, 0)\n",
    "\n",
    "    def dfs(self, left_tasks, capacity):\n",
    "        if left_tasks == 0:\n",
    "            return 0\n",
    "        if capacity == self.sessionTime and self.memo[left_tasks] != -1:\n",
    "            return self.memo[left_tasks]\n",
    "        res = (1 << 31)-1\n",
    "        picked = set()\n",
    "        for i in range(len(self.tasks)):\n",
    "            if ((1 << i) & left_tasks) and self.tasks[i] <= capacity:\n",
    "                if (self.tasks[i] in picked):\n",
    "                    continue\n",
    "                picked.add(self.tasks[i])\n",
    "\n",
    "                res = min(res, self.dfs(left_tasks ^ (1 << i),\n",
    "                          capacity-self.tasks[i]))\n",
    "        if res == (1 << 31)-1:\n",
    "            res = 1+self.dfs(left_tasks, self.sessionTime)\n",
    "        if capacity == self.sessionTime:\n",
    "            self.memo[left_tasks] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "    \n",
    "        n = len(tasks)\n",
    "        S = [0] * (1 << n)\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, 1 << i):\n",
    "                S[j | 1 << i] = S[j] + tasks[i]\n",
    "        \n",
    "\n",
    "        f = [n] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for to_task in range(1 << n):\n",
    "            sub = to_task\n",
    "            while sub:\n",
    "                if S[sub] <= sessionTime:\n",
    "                    f[to_task] = min(f[to_task], f[to_task^sub] + 1)\n",
    "                sub = (sub-1) & to_task\n",
    "        \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "    \n",
    "        n = len(tasks)\n",
    "        S = [0] * (1 << n)\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, 1 << i):\n",
    "                S[j | 1 << i] = S[j] + tasks[i]\n",
    "        \n",
    "\n",
    "        f = [n] * (1 << n)\n",
    "        f[0] = 0\n",
    "\n",
    "        # 快 to_task^sub 从 小 到 大\n",
    "        for to_task in range(1 << n):\n",
    "            if S[to_task] <= sessionTime:\n",
    "                f[to_task] = 1\n",
    "                continue\n",
    "\n",
    "            sub = to_task\n",
    "            while sub:\n",
    "                sub = (sub-1) & to_task\n",
    "                if S[sub] <= sessionTime:\n",
    "                    f[to_task] = min(f[to_task], f[to_task^sub] + 1)\n",
    "               \n",
    "        \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        states = 1 << n\n",
    "        s = [0] * states\n",
    "        for i in range(states):\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    s[i] = s[i ^ (1 <<j)] + tasks[j]\n",
    "                    break\n",
    "        f = [inf] * states\n",
    "        f[0] = 0\n",
    "        for i in range(states):\n",
    "            sub = i\n",
    "            while sub:\n",
    "                if s[sub] <= sessionTime:\n",
    "                    f[i] = min(f[i], f[i ^ sub] + 1)\n",
    "                sub = (sub - 1) & i\n",
    "        return f[states - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        dp = [0] * (1 << n)\n",
    "        for i in range(1, len(dp)):\n",
    "            # dp[i] = dp[i &(i - 1)] + tasks[int(math.log(i & (-i), 2))]\n",
    "            need = 0\n",
    "            for j in range(n):\n",
    "                if i & (1 << j):\n",
    "                    need += tasks[j]\n",
    "            \n",
    "            dp[i] = need\n",
    "\n",
    "        ans = [float('inf')] * (1 << n)\n",
    "        ans[0] = 0\n",
    "        for i in range(1, 1 << n):           \n",
    "            sub = i\n",
    "\n",
    "            if dp[sub] <= sessionTime:\n",
    "                ans[i] = ans[i ^ sub] + 1\n",
    "\n",
    "            while True:\n",
    "                sub = (sub - 1) & i \n",
    "                if dp[sub] <= sessionTime:\n",
    "                    ans[i] = min(ans[i], ans[i ^ sub] + 1)\n",
    "                if sub == 0:\n",
    "                    break\n",
    "\n",
    "\n",
    "        return ans[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "    \n",
    "        n = len(tasks)\n",
    "        S = [0] * (1 << n)\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, 1 << i):\n",
    "                S[j | 1 << i] = S[j] + tasks[i]\n",
    "        \n",
    "\n",
    "        f = [n] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for to_task in range(1 << n):\n",
    "            sub = to_task\n",
    "            while sub:\n",
    "                if S[sub] <= sessionTime:\n",
    "                    f[to_task] = min(f[to_task], f[to_task^sub] + 1)\n",
    "                sub = (sub-1) & to_task\n",
    "        \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks, sessionTime):\n",
    "        # f[mask]表示当选择任务的状态为mask时,最少需要的工作时间段\n",
    "        # mask是一个长度为n的二进制表示从低到高的第i位为 1表示第 i个任务已经完成,0表示第i个任务未完成\n",
    "        # f[mask] = f[mask\\subset] + 1(subset 中包含的任务的工作时间总和不能大于sessionTime)\n",
    "        # 预处理\n",
    "        n = len(tasks)\n",
    "        m = 1 << n # 表示任务的所有情况\n",
    "        valid = [0] * m\n",
    "        for mask in range(1,m):\n",
    "            needTime = 0\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i):\n",
    "                    needTime += tasks[i]\n",
    "            if needTime <= sessionTime:\n",
    "                valid[mask] = True\n",
    "\n",
    "        # 动态规划\n",
    "        f = [float('inf')] * m\n",
    "        f[0] = 0\n",
    "        for mask in range(1,m):\n",
    "            sub = mask\n",
    "            while sub:\n",
    "                if valid[sub]:\n",
    "                    f[mask] = min(f[mask],f[mask ^ sub] + 1)\n",
    "                sub = (sub-1)&mask\n",
    "        return f[m-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n=len(tasks)\n",
    "        f=[0]+[inf]*(2**n-1)\n",
    "        valid=[False]*(1<<n)\n",
    "        for i in range(2**n):\n",
    "            ts=0\n",
    "            for j in range(n):\n",
    "                if (i>>j)&1==1:\n",
    "                    ts+=tasks[j]\n",
    "            if ts<=sessionTime:\n",
    "                valid[i]=True \n",
    "       # print(valid)\n",
    "        \n",
    "        for mask in range(2**n):\n",
    "            subset=mask\n",
    "            while subset:\n",
    "                if valid[subset]:\n",
    "                    f[mask]=min(f[mask],f[mask^subset]+1)\n",
    "                subset=(subset-1)&mask\n",
    "            \n",
    "        #print(f)\n",
    "        return f[2**n-1]\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        m = 1 << n\n",
    "        # dp[mask]表示完成状态为mask的最少数目的工作时间段\n",
    "        # dp[mask] = dp[mask'] + 1\n",
    "        # 枚举mask\n",
    "        # 预处理 s\n",
    "        valid = [False]*m\n",
    "        for mask in range(1,m):\n",
    "            cnt = 0\n",
    "            # 枚举每一个任务\n",
    "            for i in range(n):\n",
    "                if (mask >> i)&1:\n",
    "                    cnt += tasks[i] \n",
    "            if cnt <= sessionTime:\n",
    "                valid[mask] = True\n",
    "        # 动态规划\n",
    "        dp = [n]*m\n",
    "        dp[0] = 0\n",
    "        for mask in range(1,m):\n",
    "            tmp = mask\n",
    "            while tmp > 0:\n",
    "                if valid[tmp]:\n",
    "                    dp[mask] = min(dp[mask],dp[mask^tmp] + 1)\n",
    "                tmp = (tmp-1)&mask\n",
    "        return dp[m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "    \n",
    "        n = len(tasks)\n",
    "        S = [0] * (1 << n)\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, 1 << i):\n",
    "                S[j | 1 << i] = S[j] + tasks[i]\n",
    "        \n",
    "\n",
    "        f = [n] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for to_task in range(1 << n):\n",
    "            sub = to_task\n",
    "            while sub != 0:\n",
    "                sub = (sub-1) & to_task\n",
    "                if S[to_task^sub] <= sessionTime:\n",
    "                    f[to_task] = min(f[to_task], f[sub] + 1)\n",
    "        \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks, sessionTime):\n",
    "        n = len(tasks)\n",
    "        m = 1 << n\n",
    "\n",
    "        # Preprocess all subset sums\n",
    "        subset_sums = [0] * m\n",
    "        for i in range(n):\n",
    "            for j in range(1 << i):\n",
    "                subset_sums[j | (1 << i)] = subset_sums[j] + tasks[i]\n",
    "\n",
    "        # Dynamic programming\n",
    "        f = [n] * m\n",
    "        f[0] = 0\n",
    "\n",
    "        for s in range(m):\n",
    "            # Enumerate all subsets of s\n",
    "            sub = s\n",
    "            while sub > 0:\n",
    "                # If the subset's sum is less than or equal to sessionTime, update f[s]\n",
    "                if subset_sums[sub] <= sessionTime:\n",
    "                    f[s] = min(f[s], f[s ^ sub] + 1)\n",
    "                # Get the next sub-subset\n",
    "                sub = (sub - 1) & s\n",
    "\n",
    "        return f[m - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        m = 1 << n\n",
    "        s = [0] * m\n",
    "        for i in range(n):\n",
    "            for j in range(1 << i):\n",
    "                s[(1 << i) | j] = s[j] + tasks[i]\n",
    "\n",
    "        f = [n] * m\n",
    "        f[0] = 0\n",
    "        for i in range(m):\n",
    "            sub = i\n",
    "            while sub:\n",
    "                if s[sub] <= sessionTime:\n",
    "                    f[i] = min(f[i], f[i ^ sub] + 1)\n",
    "                sub = (sub - 1) & i\n",
    "        return f[m - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        FULL = (1<<n) - 1\n",
    "        f = [float('inf')]*(FULL+1)\n",
    "        f[0] = 0\n",
    "        # f[s] 表示需要完成的任务状态为s时，需要的最少时间段.\n",
    "        # s中 1表示需要完成的任务，0表示不需要\n",
    "        # 初始s = 0，f[0] = 0。 即没有任务需要完成，那么所需时间段 = 0\n",
    "\n",
    "        # 预先计算特定状态下的任务是否超过sesstionTime\n",
    "        valid = [False]*(FULL+1)\n",
    "        for s in range(FULL+1):\n",
    "            cur_sum = 0\n",
    "            for i in range(n):\n",
    "                if s&(1<<i):\n",
    "                    cur_sum+=tasks[i]\n",
    "            if cur_sum<=sessionTime:\n",
    "                valid[s] = True\n",
    "\n",
    "        for s in range(1, FULL+1):\n",
    "            p = s\n",
    "            while p!=0:\n",
    "                if valid[p]:\n",
    "                    f[s] = min(f[s], 1+f[s^p])\n",
    "                p = (p-1)&s\n",
    "            pass\n",
    "        return f[FULL]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        # dp[mask] = dp[mask']+1\n",
    "        # 预处理\n",
    "        n = len(tasks)\n",
    "        m = 1 << n\n",
    "        valid = [False]*m\n",
    "        for mask in range(1,m):\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if (mask >> i)&1:\n",
    "                    cnt += tasks[i]\n",
    "            if cnt <= sessionTime:\n",
    "                valid[mask] = True\n",
    "        # 动态规划\n",
    "        dp = [inf]*m\n",
    "        dp[0] = 0\n",
    "        for mask in range(1,m):\n",
    "            sub = mask\n",
    "            while sub:\n",
    "                if valid[sub]:\n",
    "                    dp[mask] = min(dp[mask^sub]+1,dp[mask])\n",
    "                sub = (sub-1)&mask\n",
    "        return dp[m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        valid = [False] * (1 << n)\n",
    "        for mask in range(1, 1 << n):\n",
    "            needTime = 0\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i):\n",
    "                    needTime += tasks[i]\n",
    "            if needTime <= sessionTime:\n",
    "                valid[mask] = True\n",
    "\n",
    "        f = [float(\"inf\")] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for mask in range(1, 1 << n):\n",
    "            subset = mask\n",
    "            while subset:\n",
    "                if valid[subset]:\n",
    "                    f[mask] = min(f[mask], f[mask ^ subset] + 1)\n",
    "                subset = (subset - 1) & mask\n",
    "        \n",
    "        return f[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        dp = [0] * (1 << n)\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i] = dp[i &(i - 1)] + tasks[int(math.log(i & (-i), 2))]\n",
    "        \n",
    "\n",
    "        ans = [float('inf')] * (1 << n)\n",
    "        ans[0] = 0\n",
    "        for i in range(1, 1 << n):           \n",
    "            sub = i\n",
    "\n",
    "            if dp[sub] <= sessionTime:\n",
    "                ans[i] = ans[i ^ sub] + 1\n",
    "\n",
    "            while True:\n",
    "                sub = (sub - 1) & i \n",
    "                if dp[sub] <= sessionTime:\n",
    "                    ans[i] = min(ans[i], ans[i ^ sub] + 1)\n",
    "                if sub == 0:\n",
    "                    break\n",
    "\n",
    "\n",
    "        return ans[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        f = [(float(\"inf\"), float(\"inf\"))] * (1 << n)\n",
    "        f[0] = (1, 0)\n",
    "\n",
    "        def add(o: Tuple[int, int], x: int) -> Tuple[int, int]:\n",
    "            if o[1] + x <= sessionTime:\n",
    "                return o[0], o[1] + x\n",
    "            return o[0] + 1, x\n",
    "        \n",
    "        for mask in range(1, 1 << n):\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i):\n",
    "                    f[mask] = min(f[mask], add(f[mask ^ (1 << i)], tasks[i]))\n",
    "        \n",
    "        return f[(1 << n) - 1][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        f = [(15,20)]*(1<<(n))\n",
    "        \n",
    "        f[0] = (1,0)\n",
    "        def work(o,x):\n",
    "            if o[1]+x <= sessionTime:\n",
    "                return (o[0],o[1]+x)\n",
    "            else:\n",
    "                return (o[0]+1,x)\n",
    "        for mask in range(0,1<<n):\n",
    "            for i in range(n):\n",
    "                k = 1<<i\n",
    "                f[mask|k] = min(f[mask|k],work(f[mask],tasks[i]))\n",
    "                #print(mask,mask|k,f[mask|k])\n",
    "        return f[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        valid = set()\n",
    "        for mask in range(1 << n):\n",
    "            t = sum(x for i,x in enumerate(tasks) if mask >> i & 1)\n",
    "            if t <= sessionTime:\n",
    "                valid.add(mask)\n",
    "        \n",
    "        f = [inf]*(1 << n)\n",
    "        f[0] = 0\n",
    "        for st in range(1 << n):\n",
    "            sub = st\n",
    "            while sub:\n",
    "                if sub in valid:\n",
    "                    f[st] = min(f[st],f[st ^ sub] + 1)\n",
    "                sub = (sub - 1) & st\n",
    "        return f[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        max_state = (1 << n)\n",
    "        f = {}\n",
    "        f[0] = 0\n",
    "        q = [0]\n",
    "        l = 0\n",
    "        r = 1\n",
    "\n",
    "        while l < r:\n",
    "            now_state = q[l]\n",
    "            l += 1\n",
    "            used_part_time = f[now_state] % sessionTime\n",
    "            for index in range(n):\n",
    "                if (now_state & (1 << index)) == 0:\n",
    "                    next_state = now_state | (1 << index)\n",
    "                    if tasks[index] + used_part_time <= sessionTime:\n",
    "                        next_time = f[now_state] + tasks[index]\n",
    "                    else:\n",
    "                        next_time = f[now_state] - used_part_time + sessionTime + tasks[index]\n",
    "                    \n",
    "                    if next_state not in f:\n",
    "                        f[next_state] = next_time\n",
    "                        q.append(next_state)\n",
    "                        r += 1\n",
    "                    else:\n",
    "                        f[next_state] = min(f[next_state], next_time)\n",
    "        \n",
    "        res = f[max_state - 1] / sessionTime\n",
    "        if f[max_state - 1] % sessionTime != 0:\n",
    "            res += 1\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        # 首先这个范围是很小的 1 <= n <= 14  ；；2的14次方是比较小的 10**4左右\n",
    "        # 返回完成所有任务所需要的 最少 数目的 工作时间段    ->   最值问题，大概率是DP、贪心或者二分\n",
    "        \n",
    "        tasks.sort()\n",
    "        n = len(tasks)\n",
    "        @cache\n",
    "        def f(t):\n",
    "            if not t:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            n1 = len(t)\n",
    "            for s1 in range(1, 2**n1):\n",
    "                if sum(t[i] for i in range(n1) if s1 >> i & 1) <= sessionTime:\n",
    "                    ans = min(ans, 1+f(tuple([t[i] for i in range(n1) if s1 >> i & 1 == 0])))\n",
    "            return ans\n",
    "        \n",
    "        return f(tuple(tasks))\n",
    "                    \n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        m = 1 << n\n",
    "        f = [[inf, inf] for _ in range(m)]\n",
    "        f[0] = [1, 0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            mask = i\n",
    "            j = 0\n",
    "            while i > 0:\n",
    "                if i & 1:\n",
    "                    subset = (1 << j) ^ mask\n",
    "                    if tasks[j] + f[subset][1] <= sessionTime:\n",
    "                        a, b = f[subset][0], tasks[j] + f[subset][1]\n",
    "                    else:\n",
    "                        a, b = f[subset][0] + 1, tasks[j]\n",
    "                    \n",
    "                    if a < f[mask][0] or a == f[mask][0] and b < f[mask][1]:\n",
    "                        f[mask] = [a, b]\n",
    "                j += 1\n",
    "                i >>= 1\n",
    "        \n",
    "        return f[-1][0]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        #@functools.lru_cache()\n",
    "        dp = {}\n",
    "        def f(s, c):\n",
    "            if (s,c) in dp: return dp[(s,c)]\n",
    "            if int(s) == 0: return 1\n",
    "            v = float('inf')\n",
    "            duplicated = set()\n",
    "            for i in range(n):\n",
    "                if tasks[i] in duplicated: continue\n",
    "                if s[i] == '0': continue\n",
    "                duplicated.add(tasks[i])\n",
    "                if c >= tasks[i]:\n",
    "                    v = min(v, f(s[:i]+'0'+s[i+1:], c-tasks[i]))\n",
    "            if v == float('inf'): \n",
    "                v = min(v, 1+f(s, sessionTime))\n",
    "            dp[(s,c)] = v\n",
    "            return v\n",
    "\n",
    "        n = len(tasks)\n",
    "        return f('1'*n, sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "                n = len(tasks)\n",
    "                dp = [[0]*(sessionTime+1) for _ in range((1<<n))]\n",
    "                def f(s, c):\n",
    "                    if dp[s][c] > 0: return dp[s][c]\n",
    "                    if s == (1<<n)-1: return 1\n",
    "                    v = float('inf')\n",
    "                    for i in range(n):\n",
    "                        if (s>>i&1) == 1: continue\n",
    "                        if c >= tasks[i]:\n",
    "                            v = min(v, f(s^1<<i, c-tasks[i]))\n",
    "                    if v == float('inf'): \n",
    "                        v = min(v, 1+f(s, sessionTime))\n",
    "                    dp[s][c] = v\n",
    "                    return v\n",
    "\n",
    "                return f(0, sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "                n = len(tasks)\n",
    "                dp = [[0]*(sessionTime+1) for _ in range((1<<n))]\n",
    "                def f(s, c):\n",
    "                    if dp[s][c] > 0: return dp[s][c]\n",
    "                    if s == (1<<n)-1: return 1\n",
    "                    v = float('inf')\n",
    "                    for i in range(n):\n",
    "                        if (s>>i&1) == 1: continue\n",
    "                        if c >= tasks[i]:\n",
    "                            v = min(v, f(s^1<<i, c-tasks[i]))\n",
    "                    if v == float('inf'): \n",
    "                        v = min(v, 1+f(s, sessionTime))\n",
    "                    dp[s][c] = v\n",
    "                    return v\n",
    "\n",
    "                tasks.sort(reverse=True)\n",
    "                return f(0, sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "    \n",
    "        n = len(tasks)\n",
    "        S = [0] * (1 << n)\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, 1 << i):\n",
    "                S[j | 1 << i] = S[j] + tasks[i]\n",
    "        \n",
    "\n",
    "\n",
    "        # @cache \n",
    "        # def Sum(n):\n",
    "        #     if n == 0:\n",
    "        #         return 0\n",
    "        #     b = n & (-n)\n",
    "        #     return Sum(n&(n-1)) + tasks[b.bit_length()-1]\n",
    "        # for i in range(1, (1 << n)-1):\n",
    "        #     Sum(i)\n",
    "        \n",
    "         \n",
    "\n",
    "        @cache\n",
    "        def f(to_task):\n",
    "            if to_task == 0:\n",
    "                return 0 \n",
    "            \n",
    "            if S[to_task] <= sessionTime:\n",
    "                return 1\n",
    "            \n",
    "            res = float('inf')\n",
    "            sub = to_task\n",
    "\n",
    "\n",
    "            while sub != 0:\n",
    "                sub = (sub-1) & to_task\n",
    "                if S[to_task^sub] <= sessionTime:\n",
    "                    res = min(res, f(sub) + 1)\n",
    "            return res\n",
    "        \n",
    "        return f((1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        u = (1 << n) - 1\n",
    "        time = {}\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1:\n",
    "                    cur |= 1 << j\n",
    "            mask = cur\n",
    "            while mask:\n",
    "                s = 0\n",
    "                if mask not in time:\n",
    "                    for j in range(n):\n",
    "                        if (mask >> j) & 1 == 1:\n",
    "                            s += tasks[j]\n",
    "                    time[mask] = s\n",
    "                else:\n",
    "                    s = time[mask]\n",
    "\n",
    "                if s <= sessionTime:\n",
    "                    ans = min(ans, dfs(cur ^ mask) + 1)\n",
    "                mask = (mask - 1) & cur\n",
    "            return ans\n",
    "        return dfs(u)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\r\n",
    "        # 状压dp \r\n",
    "        n = len(tasks)\r\n",
    "        sm = []\r\n",
    "        for i in range(1 << n):\r\n",
    "            s = 0\r\n",
    "            for j in range(n):\r\n",
    "                if (i >> j) & 1:\r\n",
    "                    s += tasks[j]\r\n",
    "            sm.append(s)\r\n",
    "        print(sm)\r\n",
    "        @cache \r\n",
    "        def dfs(s) -> int:\r\n",
    "            if s == 0:\r\n",
    "                return 0\r\n",
    "            sub = s \r\n",
    "            res = inf\r\n",
    "            while sub:\r\n",
    "                if sm[sub] <= sessionTime:\r\n",
    "                    res = min(res, dfs(s ^ sub) + 1)\r\n",
    "                sub = (sub - 1) & s\r\n",
    "            return res \r\n",
    "        return dfs((1 << n) - 1)\r\n",
    "\r\n",
    "\r\n",
    "            \r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\r\n",
    "        # 状压dp \r\n",
    "        n = len(tasks)\r\n",
    "        sm = []\r\n",
    "        for i in range(1 << n):\r\n",
    "            s = 0\r\n",
    "            for j in range(n):\r\n",
    "                if (i >> j) & 1:\r\n",
    "                    s += tasks[j]\r\n",
    "            sm.append(s)\r\n",
    "\r\n",
    "        @cache \r\n",
    "        def dfs(s) -> int:\r\n",
    "            if s == 0:\r\n",
    "                return 0\r\n",
    "            res = inf\r\n",
    "            sub = s\r\n",
    "            while sub:\r\n",
    "                if sm[sub] <= sessionTime:\r\n",
    "                    res = min(res, 1 + dfs(s ^ sub))\r\n",
    "                sub = (sub - 1) & s\r\n",
    "            return res \r\n",
    "        return dfs((1 << n) - 1)\r\n",
    "\r\n",
    "\r\n",
    "            \r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\r\n",
    "        # 状压dp \r\n",
    "        n = len(tasks)\r\n",
    "        sm = []\r\n",
    "        for i in range(1 << n):\r\n",
    "            s = 0\r\n",
    "            for j in range(n):\r\n",
    "                if (i >> j) & 1:\r\n",
    "                    s += tasks[j]\r\n",
    "            sm.append(s)\r\n",
    "        # print(sm)\r\n",
    "        @cache \r\n",
    "        def dfs(s) -> int:\r\n",
    "            if s == 0:\r\n",
    "                return 0\r\n",
    "            sub = s \r\n",
    "            res = inf\r\n",
    "            while sub:\r\n",
    "                if sm[sub] <= sessionTime:\r\n",
    "                    res = min(res, dfs(s ^ sub) + 1)\r\n",
    "                sub = (sub - 1) & s\r\n",
    "            return res \r\n",
    "        return dfs((1 << n) - 1)\r\n",
    "\r\n",
    "\r\n",
    "            \r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\r\n",
    "        # 状压dp \r\n",
    "        n = len(tasks)\r\n",
    "        sm = []\r\n",
    "        for i in range(1 << n):\r\n",
    "            s = 0\r\n",
    "            for j in range(n):\r\n",
    "                if (i >> j) & 1:\r\n",
    "                    s += tasks[j]\r\n",
    "            sm.append(s)\r\n",
    "        # print(sm)\r\n",
    "        @cache \r\n",
    "        def dfs(s) -> int:\r\n",
    "            if s == 0:\r\n",
    "                return 0\r\n",
    "            sub = s \r\n",
    "            res = inf\r\n",
    "            while sub:\r\n",
    "                if sm[sub] <= sessionTime:\r\n",
    "                    res = min(res, dfs(s ^ sub) + 1)\r\n",
    "                sub = (sub - 1) & s\r\n",
    "            return res \r\n",
    "        return dfs((1 << n) - 1)\r\n",
    "\r\n",
    "\r\n",
    "            \r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        @cache\n",
    "        def f(mask:int,time:int)->int:\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            res = 1\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1:\n",
    "                    if time >= tasks[i]:\n",
    "                        res -= 1\n",
    "                        break\n",
    "            if res:\n",
    "                time = sessionTime\n",
    "            mn = inf\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1:\n",
    "                    if time >= tasks[i]:\n",
    "                        mn = min(mn,f(mask ^ (1<<i),time-tasks[i]))\n",
    "            res += mn\n",
    "            return res\n",
    "        return f((1<<n)-1,sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state, re):\n",
    "            if state.bit_count() == n:\n",
    "                return 0\n",
    "            \n",
    "            res = inf\n",
    "            if re != sessionTime:\n",
    "                res = 1 + dfs(state, sessionTime)\n",
    "            if re:\n",
    "                for i in range(n):\n",
    "                    if state & 1 << i == 0 and re >= tasks[i]:\n",
    "                        res = min(res, dfs(state | 1 << i, re - tasks[i]))\n",
    "            \n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "                #@functools.lru_cache()\n",
    "                dp = {}\n",
    "                def f(s, c):\n",
    "                    if (s,c) in dp: return dp[(s,c)]\n",
    "                    if s == (1<<n)-1: return 1\n",
    "                    v = float('inf')\n",
    "                    for i in range(n):\n",
    "                        if (s>>i&1) == 1: continue\n",
    "                        if c >= tasks[i]:\n",
    "                            v = min(v, f(s^1<<i, c-tasks[i]))\n",
    "                    if v == float('inf'): \n",
    "                        v = min(v, 1+f(s, sessionTime))\n",
    "                    dp[(s,c)] = v\n",
    "                    return v\n",
    "\n",
    "                n = len(tasks)\n",
    "                return f(0, sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(remain, status):\n",
    "            if status == 2 ** n - 1 :\n",
    "                return 1\n",
    "            curr_min = float(inf)\n",
    "            remain_too_small = True\n",
    "            for i,j in enumerate(tasks):\n",
    "                if status & (1 << i) == 0 and j <= remain:\n",
    "                    curr_min = min(curr_min, helper(remain - j, status | (1 << i)))\n",
    "                    remain_too_small = False\n",
    "            if remain_too_small:\n",
    "                curr_min = min(curr_min, helper(sessionTime, status) + 1)     \n",
    "            return curr_min            \n",
    "        return helper(sessionTime, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "                #@functools.lru_cache()\n",
    "                dp = {}\n",
    "                def f(s, c):\n",
    "                    if (s,c) in dp: return dp[(s,c)]\n",
    "                    if int(s) == 0: return 1\n",
    "                    v = float('inf')\n",
    "                    flag = True\n",
    "                    for i in range(n):\n",
    "                        if s[i] == '0': continue\n",
    "                        if c >= tasks[i]:\n",
    "                            v = min(v, f(s[:i]+'0'+s[i+1:], c-tasks[i]))\n",
    "                            flag = False\n",
    "                    if flag: v = min(v, 1+f(s, sessionTime))\n",
    "                    dp[(s,c)] = v\n",
    "                    return v\n",
    "\n",
    "                n = len(tasks)\n",
    "                return f('1'*n, sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "                #@functools.lru_cache()\n",
    "                dp = {}\n",
    "                def f(s, c):\n",
    "                    if (s,c) in dp: return dp[(s,c)]\n",
    "                    if int(s) == 0: return 1\n",
    "                    v = float('inf')\n",
    "                    for i in range(n):\n",
    "                        if s[i] == '0': continue\n",
    "                        if c >= tasks[i]:\n",
    "                            v = min(v, f(s[:i]+'0'+s[i+1:], c-tasks[i]))\n",
    "                    if v == float('inf'): \n",
    "                        v = min(v, 1+f(s, sessionTime))\n",
    "                    dp[(s,c)] = v\n",
    "                    return v\n",
    "\n",
    "                n = len(tasks)\n",
    "                return f('1'*n, sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        @lru_cache(None)\n",
    "        def dfs(st,t):\n",
    "            if st == 0:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for i,x in enumerate(tasks):\n",
    "                if st >> i & 1:\n",
    "                    if t + x <= sessionTime:\n",
    "                        ans = min(ans,dfs(st ^ (1 << i),t + x))\n",
    "                    else:\n",
    "                        ans = min(ans,dfs(st ^ (1 << i),x) + 1)\n",
    "            return ans\n",
    "\n",
    "        return dfs((1 << n) - 1,0) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        if sum(tasks) <= sessionTime:\n",
    "            return 1\n",
    "        n = len(tasks)\n",
    "        @lru_cache(None)\n",
    "        def dp(state, remain):\n",
    "            if state == 0:\n",
    "                # if remain >= 0:\n",
    "                return 1\n",
    "\n",
    "            ans = 14\n",
    "            for i in range(n):\n",
    "                if (1 << i) & state:\n",
    "                    if remain - tasks[i] >= 0:\n",
    "                        ans = min(ans, dp((1 << i) ^ state, remain - tasks[i]))\n",
    "                    else:\n",
    "                        ans = min(ans, dp((1 << i) ^ state, sessionTime - tasks[i]) + 1)\n",
    "\n",
    "            return ans\n",
    "        \n",
    "        return dp((1 << n) - 1, sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        # 方法1、回溯\n",
    "        @cache\n",
    "        def dfs(missionCollection,remainingHour):\n",
    "            if not missionCollection:\n",
    "                return 0\n",
    "            ans = n\n",
    "            for i in range(n):\n",
    "                if missionCollection & (1 <<i):\n",
    "                    if remainingHour >= tasks[i]:\n",
    "                        ans = min(ans,dfs(missionCollection ^ (1 << i),remainingHour - tasks[i]))\n",
    "                    else:\n",
    "                        ans = min(ans,1 + dfs(missionCollection ^ (1 << i),sessionTime - tasks[i]))\n",
    "            return ans\n",
    "\n",
    "        n = len(tasks)\n",
    "        u = (1 << n) - 1\n",
    "        return 1 + dfs(u,sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        # 当前状态，当前时间time最少需要几轮才能完成任务\n",
    "        @cache\n",
    "        def f(mask:int,time:int)->int:\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            res = inf\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1:\n",
    "                    # 时间不够用，开启下一轮\n",
    "                    if time < tasks[i]:\n",
    "                        res = min(res,f(mask ^ (1<<i),sessionTime-tasks[i])+1)\n",
    "                    # 时间够用不需要下一轮\n",
    "                    else:\n",
    "                        res = min(res,f(mask ^ (1<<i),time-tasks[i]))\n",
    "            return res\n",
    "        return f((1<<n)-1,sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        \n",
    "        n = len(tasks)\n",
    "        \n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(state, rest):\n",
    "            if not state:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for i in range(n):\n",
    "                if state & (1<<i):\n",
    "                    if rest >= tasks[i]:\n",
    "                        cur = dfs(state^(1<<i), rest-tasks[i])\n",
    "                    else:\n",
    "                        cur = 1+dfs(state^(1<<i), sessionTime-tasks[i])\n",
    "                    if cur < res:\n",
    "                        res = cur\n",
    "            return res\n",
    "        \n",
    "        \n",
    "        return dfs((1<<n)-1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], sessionTime: int) -> int:\n",
    "        n = len(tasks)\n",
    "        # 当前状态，当前时间time最少需要几轮才能完成任务\n",
    "        @cache\n",
    "        def f(mask:int,time:int)->int:\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            res = inf\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1:\n",
    "                    # 时间不够用，开启下一轮\n",
    "                    if time < tasks[i]:\n",
    "                        res = min(res,f(mask ^ (1<<i),sessionTime-tasks[i])+1)\n",
    "                    # 时间够用不需要下一轮\n",
    "                    else:\n",
    "                        res = min(res,f(mask ^ (1<<i),time-tasks[i]))\n",
    "            return res\n",
    "        return f((1<<n)-1,sessionTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSessions(self, tasks: List[int], s: int) -> int:\n",
    "        n = len(tasks)\n",
    "        @cache\n",
    "        def dfs(mask, tot):\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            res = 10**18\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    x = tasks[i]\n",
    "                    if x > tot:\n",
    "                        res = min(res, dfs(mask ^ (1 << i), s - x) + 1)\n",
    "                    else:\n",
    "                        res = min(res, dfs(mask ^ (1 << i), tot - x))\n",
    "            return res\n",
    "        return dfs((1 << n) - 1, s) + 1\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
